home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 March / macformat-022.iso / Shareware City / Developers / GNU Diff Sources / GNU DIFF 1.15b Sources / diff3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-11-02  |  45.6 KB  |  1,708 lines  |  [TEXT/ALFA]
  1. /* Three-way file comparison program (diff3) for Project GNU
  2.    Copyright (C) 1988, 1989 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 1, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18.  
  19. /* Written by Randy Smith */
  20.  
  21. #ifdef __STDC__
  22. #define VOID void
  23. #else
  24. #define VOID char
  25. #endif
  26.  
  27. /* 
  28.  * Include files.
  29.  */
  30. #include <stdio.h>
  31. #include <ctype.h>
  32. #ifndef    THINK_C
  33. #include <sys/types.h>
  34. #include <sys/stat.h>
  35. #endif
  36.  
  37. #ifdef USG
  38. #include <fcntl.h>
  39.  
  40. /* Define needed BSD functions in terms of sysV library.  */
  41.  
  42. #define bcmp(s1,s2,n)    memcmp((s1),(s2),(n))
  43. #define bzero(s,n)    memset((s),0,(n))
  44.  
  45. #ifndef XENIX
  46. #define dup2(f,t)    (close(t),fcntl((f),F_DUPFD,(t)))
  47. #endif
  48.  
  49. #define vfork    fork
  50.  
  51. #else /* not USG */
  52. #ifndef    THINK_C
  53. #include <sys/wait.h>
  54. #endif
  55. #endif /* not USG */
  56.  
  57. #ifndef WEXITSTATUS
  58. #define WEXITSTATUS(stat_val) ((unsigned)(stat_val) >> 8)
  59. #undef WIFEXITED /* Avoid 4.3BSD incompatibility with Posix.  */
  60. #endif
  61. #ifndef WIFEXITED
  62. #define WIFEXITED(stat_val) (((stat_val) & 255) == 0)
  63. #endif
  64.  
  65. #ifdef sparc
  66. /* vfork clobbers registers on the Sparc, so don't use it.  */
  67. #define vfork fork
  68. #endif
  69.  
  70.  
  71. #define    GDIFF3_MAIN
  72. #include    "diff.h"
  73. #include    "diff3.h"
  74.  
  75. #ifndef    EXCLUDE_MAIN
  76.  
  77. #ifdef    DIRECT_DIFF
  78. static    void
  79. copy_file_data (struct file_data *src_file, struct file_data *dest_file)
  80.     {
  81.     dest_file->desc = src_file->desc;
  82.     dest_file->name = src_file->name;
  83.     dest_file->stat = src_file->stat;
  84.     dest_file->dir_p = src_file->dir_p;
  85.     dest_file->buffer = src_file->buffer;
  86.     dest_file->bufsize = src_file->bufsize;
  87.     dest_file->buffered_chars = src_file->buffered_chars;
  88.     dest_file->linbufsize = src_file->linbufsize;
  89.     dest_file->buffered_lines = src_file->buffered_lines;
  90.     dest_file->already_read_in = src_file->already_read_in;
  91.     }
  92. #endif    DIRECT_DIFF
  93.  
  94. /*
  95.  * Main program.  Calls diff twice on two pairs of input files,
  96.  * combines the two diffs, and outputs them.
  97.  */
  98. #ifdef    DIRECT_DIFF
  99. main_diff3 (argc, argv)
  100. #else    DIRECT_DIFF
  101. main (argc, argv)
  102. #endif    DIRECT_DIFF
  103.      int argc;
  104.      char **argv;
  105. {
  106.     int c, i;
  107.     int mapping[3];
  108.   int rev_mapping[3];
  109.   int incompat;
  110.   int overlaps_found;
  111.   struct diff_block *thread1, *thread2;
  112.   struct diff3_block *diff;
  113.   int tag_count = 0;
  114.   /* Element 0 is for file 0, element 1 is for file 2.  */
  115.   char *tag_strings[2];
  116.   extern char *optarg;
  117.   char *commonname;
  118.   struct stat statb;
  119.  
  120.     incompat = 0;
  121.   tag_strings[0] = tag_strings[1] = 0;
  122.  
  123.   argv0 = argv[0];
  124.   
  125.   while ((c = getopt (argc, argv, "aeimx3EXL:")) != EOF)
  126.     {
  127.       switch (c)
  128.     {
  129.     case 'a':
  130.       always_text = 1;
  131.       break;
  132.     case 'x':
  133.       dont_write_simple = 1;
  134.       incompat++;
  135.       break;
  136.     case '3':
  137.       dont_write_overlap = 1;
  138.       incompat++;
  139.       break;
  140.     case 'i':
  141.       finalwrite = 1;
  142.       break;
  143.     case 'm':
  144.       merge = 1;
  145.       break;
  146.     case 'X':
  147.       dont_write_simple = 1;
  148.       /* Falls through */
  149.     case 'E':
  150.       flagging = 1;
  151.       /* Falls through */
  152.     case 'e':
  153.       incompat++;
  154.       break;
  155.     case 'L':
  156.       /* Handle one or two -L arguments.  */
  157.       if (tag_count < 2)
  158.         {
  159.           tag_strings[tag_count++] = optarg;
  160.           break;
  161.         }
  162.       /* Falls through */
  163.     case '?':
  164.     default:
  165.       usage (); return 1;
  166.       /* NOTREACHED */
  167.     }
  168.     }
  169.  
  170.   edscript = incompat & ~merge;  /* -eExX3 without -m implies ed script.  */
  171.   flagging |= ~incompat & merge;  /* -m without -eExX3 implies -E.  */
  172.   
  173.   if (incompat > 1  /* Ensure at most one of -eExX3.  */
  174.       || finalwrite & (~incompat | merge)
  175.         /* -i needs one of -eExX3; -i -m would rewrite input file.  */
  176.       || tag_count && ! flagging /* -L requires one of -EX.  */
  177.       || argc - optind != 3)
  178.     { usage (); return 1; }
  179.     
  180.  
  181.   if (tag_strings[0] == 0)
  182.     tag_strings[0] = argv[optind];
  183.   if (tag_strings[1] == 0)
  184.     tag_strings[1] = argv[optind + 2];
  185.  
  186.     if (*argv[optind] == '-' && *(argv[optind] + 1) == '\0')
  187.     {
  188.       /* Sigh.  We've got standard input as the first arg. We can't */
  189.       /* call diff twice on stdin */
  190.       if (! strcmp (argv[optind + 1], "-") || ! strcmp (argv[optind + 2], "-"))
  191.     fatal ("`-' specified for more than one input file");
  192.       mapping[0] = 1;
  193.       mapping[1] = 2;
  194.       mapping[2] = 0;
  195.       rev_mapping[1] = 0;
  196.       rev_mapping[2] = 1;
  197.       rev_mapping[0] = 2;
  198.     }
  199.   else
  200.     {
  201.       /* Normal, what you'd expect */
  202.       mapping[0] = 0;
  203.       mapping[1] = 1;
  204.       mapping[2] = 2;
  205.       rev_mapping[0] = 0;
  206.       rev_mapping[1] = 1;
  207.       rev_mapping[2] = 2;
  208.     }
  209.  
  210.   for (i = 0; i < 3; i++)
  211.     if (argv[optind + i][0] != '-' || argv[optind + i][1] != '\0')
  212.       if (stat (argv[optind + i], &statb) < 0)
  213.     perror_with_exit (argv[optind + i]);
  214.       else if ((statb.st_mode & S_IFMT) == S_IFDIR)
  215.     {
  216.       fpout (stderr, "%s: %s: Is a directory\n", argv0,
  217.            argv[optind + i]);
  218.       exit (2);
  219.     }
  220.  
  221.  
  222.   commonname = argv[optind + rev_mapping[0]];
  223.  
  224. #ifdef    DIRECT_DIFF
  225.     {
  226.         int    error;
  227.         struct file_data inf[4];
  228.         int    file_differs;
  229.     
  230.         line_end_char = NEWLINE;
  231.     
  232.         bzero (&inf, sizeof(inf));
  233.         
  234.         always_text_flag = always_text;
  235.         
  236.         inf[2].name = inf[0].name = commonname;
  237.         inf[1].name = argv[optind + rev_mapping[1]];
  238.         inf[3].name = argv[optind + rev_mapping[2]];
  239.     
  240.         error = open_file_pair (&inf[0], NULL, commonname, NULL, argv[optind + rev_mapping[1]]);
  241.         
  242.         if ( error != 0 || inf[0].dir_p || inf[1].dir_p )
  243.         {
  244.             goto    error_or_done;
  245.         }
  246.  
  247.         thread1 = diff_2_files_no_print(&inf[0], &file_differs);
  248.  
  249.         /*
  250.          * Close the other two file descriptors, since we are done with them.
  251.          */
  252.         if (inf[0].desc >= 0)
  253.             close (inf[0].desc);
  254.         if (inf[1].desc >= 0)
  255.             close (inf[1].desc);
  256.         inf[0].desc = inf[1].desc = -1;
  257.  
  258.         copy_file_data (&inf[0], &inf[2]);
  259.     
  260.         error = open_file_pair (&inf[2], NULL, commonname, NULL, argv[optind + rev_mapping[2]]);
  261.         if ( error != 0 || inf[2].dir_p || inf[3].dir_p )
  262.         {
  263.             goto    error_or_done;
  264.         }
  265.  
  266.         thread2 = diff_2_files_no_print(&inf[2], &file_differs);
  267.     
  268.     error_or_done:
  269.         /* Save the file info in these globals so the printing routines can have access
  270.            to the original text of the files. */
  271.         diff3_file_data[0] = inf[0];
  272.         diff3_file_data[1] = inf[1];
  273.         diff3_file_data[2] = inf[3];
  274.  
  275.         if ( inf[0].desc >= 0)
  276.             close (inf[0].desc);
  277.         if ( inf[1].desc >= 0)
  278.             close (inf[1].desc);
  279.         if ( inf[2].desc >= 0)
  280.             close (inf[2].desc);
  281.         if ( inf[3].desc >= 0)
  282.             close (inf[3].desc);
  283.  
  284.         if ( error )
  285.             return (error);
  286.     }
  287. #else    DIRECT_DIFF
  288.         thread1 = process_diff (commonname, argv[optind + rev_mapping[1]]);
  289.         thread2 = process_diff (commonname, argv[optind + rev_mapping[2]]);
  290. #endif    DIRECT_DIFF
  291.     diff = make_3way_diff (thread1, thread2);
  292.   if (edscript)
  293.     overlaps_found
  294.             = output_diff3_edscript (stdout, diff, mapping, rev_mapping,
  295.                    tag_strings[0], argv[optind+1], tag_strings[1]);
  296.   else if (merge)
  297.     {
  298.       if (! freopen (commonname, "r", stdin))
  299.     perror_with_exit (commonname);
  300.       overlaps_found
  301.     = output_diff3_merge (stdin, stdout, diff, mapping, rev_mapping,
  302.                   tag_strings[0], argv[optind+1], tag_strings[1]);
  303.       if (ferror (stdin))
  304.     fatal ("read error");
  305.     }
  306.         else
  307.         {
  308.             output_diff3 ( stdout, diff, mapping, rev_mapping);
  309.       overlaps_found = 0;
  310.         }
  311.  
  312.   if (ferror (stdout) || fflush (stdout) != 0)
  313.     fatal ("write error");
  314.     exit (overlaps_found);
  315. }
  316.       
  317. /*
  318.  * Explain, patiently and kindly, how to use this program.  Then exit.
  319.  */
  320. static    void
  321. usage ()
  322. {
  323.   fpout (stderr, "Usage:\t%s [-exEX3 [-i | -m] [-L label1 -L label3]] file1 file2 file3\n",
  324.        argv0);
  325.   fpout (stderr, "\tOnly one of [exEX3] allowed\n");
  326. //  exit (2);
  327. }
  328. #endif    EXCLUDE_MAIN
  329.  
  330. /*
  331.  * Routines that combine the two diffs together into one.  The
  332.  * algorithm used follows:
  333.  *
  334.  *   File0 is shared in common between the two diffs.
  335.  *   Diff01 is the diff between 0 and 1.
  336.  *   Diff02 is the diff between 0 and 2.
  337.  *
  338.  *     1) Find the range for the first block in File0.
  339.  *          a) Take the lowest of the two ranges (in File0) in the two
  340.  *             current blocks (one from each diff) as being the low
  341.  *             water mark.  Assign the upper end of this block as
  342.  *             being the high water mark and move the current block up
  343.  *             one.  Mark the block just moved over as to be used.
  344.  *        b) Check the next block in the diff that the high water
  345.  *             mark is *not* from.  
  346.  *           
  347.  *           *If* the high water mark is above
  348.  *             the low end of the range in that block, 
  349.  * 
  350.  *               mark that block as to be used and move the current
  351.  *                 block up.  Set the high water mark to the max of
  352.  *                 the high end of this block and the current.  Repeat b.
  353.  * 
  354.  *       2) Find the corresponding ranges in Files1 (from the blocks
  355.  *          in diff01; line per line outside of diffs) and in File2.
  356.  *          Create a diff3_block, reserving space as indicated by the ranges.
  357.  *        
  358.  *     3) Copy all of the pointers for file0 in.  At least for now,
  359.  *          do bcmp's between corresponding strings in the two diffs.
  360.  *        
  361.  *     4) Copy all of the pointers for file1 and 2 in.  Get what you
  362.  *          need from file0 (when there isn't a diff block, it's
  363.  *          identical to file0 within the range between diff blocks).
  364.  *        
  365.  *     5) If the diff blocks you used came from only one of the two
  366.  *         strings of diffs, then that file (i.e. the one other than
  367.  *         file 0 in that diff) is the odd person out.  If you used
  368.  *         diff blocks from both sets, check to see if files 1 and 2 match:
  369.  *        
  370.  *            Same number of lines?  If so, do a set of bcmp's (if a
  371.  *          bcmp matches; copy the pointer over; it'll be easier later
  372.  *          if you have to do any compares).  If they match, 1 & 2 are
  373.  *          the same.  If not, all three different.
  374.  * 
  375.  *   Then you do it again, until you run out of blocks. 
  376.  * 
  377.  */
  378.  
  379. /* 
  380.  * This routine makes a three way diff (chain of diff3_block's) from two
  381.  * two way diffs (chains of diff_block's).  It is assumed that each of
  382.  * the two diffs passed are off of the same file (i.e. that each of the
  383.  * diffs were made "from" the same file).  The three way diff pointer
  384.  * returned will have numbering 0--the common file, 1--the other file
  385.  * in diff1, and 2--the other file in diff2.
  386.  */
  387. struct diff3_block *
  388. make_3way_diff (thread1, thread2)
  389.      struct diff_block *thread1, *thread2;
  390. {
  391. /*
  392.  * This routine works on the two diffs passed to it as threads.
  393.  * Thread number 0 is diff1, thread number 1 is diff2.  The USING
  394.  * array is set to the base of the list of blocks to be used to
  395.  * construct each block of the three way diff; if no blocks from a
  396.  * particular thread are to be used, that element of the using array
  397.  * is set to 0.  The elements LAST_USING array are set to the last
  398.  * elements on each of the using lists.
  399.  *
  400.  * The HIGH_WATER_MARK is set to the highest line number in File 0
  401.  * described in any of the diffs in either of the USING lists.  The
  402.  * HIGH_WATER_THREAD names the thread.  Similarly the BASE_WATER_MARK
  403.  * and BASE_WATER_THREAD describe the lowest line number in File 0
  404.  * described in any of the diffs in either of the USING lists.  The
  405.  * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was
  406.  * taken. 
  407.  *
  408.  * The HIGH_WATER_DIFF should always be equal to LAST_USING
  409.  * [HIGH_WATER_THREAD].  The OTHER_DIFF is the next diff to check for
  410.  * higher water, and should always be equal to
  411.  * CURRENT[HIGH_WATER_THREAD ^ 0x1].  The OTHER_THREAD is the thread
  412.  * in which the OTHER_DIFF is, and hence should always be equal to
  413.  * HIGH_WATER_THREAD ^ 0x1.
  414.  *
  415.  * The variable LAST_DIFF is kept set to the last diff block produced
  416.  * by this routine, for line correspondence purposes between that diff
  417.  * and the one currently being worked on.  It is initialized to
  418.  * ZERO_DIFF before any blocks have been created.
  419.  */
  420.  
  421.   struct diff_block
  422.     *using[2],
  423.     *last_using[2],
  424.     *current[2];
  425.  
  426.     LONG
  427.         high_water_mark;
  428.  
  429.   int
  430.     high_water_thread,
  431.     base_water_thread,
  432.     other_thread;
  433.  
  434.   struct diff_block
  435.     *high_water_diff,
  436.     *other_diff;
  437.  
  438.   struct diff3_block
  439.     *result,
  440.     *tmpblock,
  441.     *result_last,
  442.     *last_diff;
  443.  
  444.   static struct diff3_block zero_diff = {
  445.         (struct diff3_block *) 0,
  446.       ERROR,
  447.         { {0, 0}, {0, 0}, {0, 0} }
  448. #ifndef    DIRECT_DIFF
  449.       { (char **) 0, (char **) 0, (char **) 0 },
  450.       { (LONG *) 0, (LONG *) 0, (LONG *) 0 },
  451. #endif
  452.       };
  453.  
  454.   /* Initialization */
  455.   result = result_last = (struct diff3_block *) 0;
  456.   current[0] = thread1; current[1] = thread2;
  457.   last_diff = &zero_diff;
  458.  
  459.   /* Sniff up the threads until we reach the end */
  460.  
  461.   while (current[0] || current[1])
  462.     {
  463.       using[0] = using[1] = last_using[0] = last_using[1] =
  464.     (struct diff_block *) 0;
  465.  
  466.       /* Setup low and high water threads, diffs, and marks.  */
  467.       if (!current[0])
  468.     base_water_thread = 1;
  469.       else if (!current[1])
  470.     base_water_thread = 0;
  471.       else
  472.     base_water_thread =
  473.       (D_LOWLINE (current[0], FILE0) > D_LOWLINE (current[1], FILE0));
  474.  
  475.       high_water_thread = base_water_thread;
  476.       
  477.       high_water_diff = current[high_water_thread];
  478.     
  479. #if 0
  480.       /* low and high waters start off same diff */
  481.       base_water_mark = D_LOWLINE (high_water_diff, FILE0);
  482. #endif
  483.  
  484.       high_water_mark = D_HIGHLINE (high_water_diff, FILE0);
  485.  
  486.       /* Make the diff you just got info from into the using class */
  487.       using[high_water_thread]
  488.     = last_using[high_water_thread]
  489.     = high_water_diff;
  490.         current[high_water_thread] = high_water_diff->next;
  491.         last_using[high_water_thread]->next
  492.     = (struct diff_block *) 0;
  493.  
  494.       /* And mark the other diff */
  495.       other_thread = high_water_thread ^ 0x1;
  496.       other_diff = current[other_thread];
  497.  
  498.       /* Shuffle up the ladder, checking the other diff to see if it
  499.          needs to be incorporated */
  500.       while (other_diff
  501.          && D_LOWLINE (other_diff, FILE0) <= high_water_mark + 1)
  502.     {
  503.  
  504.       /* Incorporate this diff into the using list.  Note that
  505.          this doesn't take it off the current list */
  506.       if (using[other_thread])
  507.                 last_using[other_thread]->next = other_diff;
  508.       else
  509.         using[other_thread] = other_diff;
  510.       last_using[other_thread] = other_diff;
  511.  
  512.       /* Take it off the current list.  Note that this following
  513.          code assumes that other_diff enters it equal to
  514.          current[high_water_thread ^ 0x1] */
  515.       current[other_thread]
  516.                 = current[other_thread]->next;
  517.             other_diff->next
  518.         = (struct diff_block *) 0;
  519.  
  520.       /* Set the high_water stuff
  521.          If this comparison is equal, then this is the last pass
  522.          through this loop; since diff blocks within a given
  523.          thread cannot overlap, the high_water_mark will be
  524.          *below* the range_start of either of the next diffs. */
  525.  
  526.       if (high_water_mark < D_HIGHLINE (other_diff, FILE0))
  527.         {
  528.           high_water_thread ^= 1;
  529.           high_water_diff = other_diff;
  530.           high_water_mark = D_HIGHLINE (other_diff, FILE0);
  531.         }
  532.  
  533.       /* Set the other diff */
  534.       other_thread = high_water_thread ^ 0x1;
  535.       other_diff = current[other_thread];
  536.     }
  537.  
  538.       /* The using lists contain a list of all of the blocks to be
  539.          included in this diff3_block.  Create it.  */
  540.  
  541.       tmpblock = using_to_diff3_block (using, last_using,
  542.                        base_water_thread, high_water_thread,
  543.                        last_diff);
  544.  
  545. #ifdef    DIRECT_DIFF
  546.     /*
  547.      * We might as well dispose of the blocks that we are finished with as we go along.
  548.      */
  549.     dispose_script (using[0]);
  550.     dispose_script (using[1]);
  551. #endif    DIRECT_DIFF
  552.  
  553.       if (!tmpblock)
  554.         {
  555.     fatal ("internal: screwup in format of diff blocks");
  556.             return (NULL);    /* Result value NULL means there was an error */
  557.         }
  558.  
  559.       /* Put it on the list */
  560.       if (result)
  561.             result_last->next = tmpblock;
  562.       else
  563.     result = tmpblock;
  564.       result_last = tmpblock;
  565.  
  566.       /* Setup corresponding lines correctly */
  567.       last_diff = tmpblock;
  568.     }
  569.   return result;
  570. }
  571.  
  572. /*
  573.  * using_to_diff3_block:
  574.  *   This routine takes two lists of blocks (from two separate diff
  575.  * threads) and puts them together into one diff3 block.
  576.  * It then returns a pointer to this diff3 block or 0 for failure.
  577.  *
  578.  * All arguments besides using are for the convenience of the routine;
  579.  * they could be derived from the using array.
  580.  * LAST_USING is a pair of pointers to the last blocks in the using
  581.  * structure.
  582.  * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest
  583.  * and highest line numbers for File0.
  584.  * last_diff contains the last diff produced in the calling routine.
  585.  * This is used for lines mappings which would still be identical to
  586.  * the state that diff ended in.
  587.  *
  588.  * A distinction should be made in this routine between the two diffs
  589.  * that are part of a normal two diff block, and the three diffs that
  590.  * are part of a diff3_block.
  591.  */
  592. struct diff3_block *
  593. using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff)
  594.      struct diff_block
  595.        *using[2],
  596.        *last_using[2];
  597.      int low_thread, high_thread;
  598.      struct diff3_block *last_diff;
  599. {
  600.     LONG lowc, highc, low1, high1, low2, high2;
  601.   struct diff3_block *result;
  602. #ifndef    DIRECT_DIFF
  603.     struct diff_block *ptr;
  604.     LONG i;
  605.     LONG current0line;
  606. #endif
  607.   
  608.   /* Find the range in file0 */
  609.   lowc = using[low_thread]->ranges[0][START];
  610.   highc = last_using[high_thread]->ranges[0][END];
  611.  
  612.   /* Find the ranges in the other files.
  613.      If using[x] is null, that means that the file to which that diff
  614.      refers is equivalent to file 0 over this range */
  615.   
  616.   if (using[0])
  617.     {
  618.       low1 = D_LOW_MAPLINE (using[0], FILE0, FILE1, lowc);
  619.       high1 = D_HIGH_MAPLINE (last_using[0], FILE0, FILE1, highc); 
  620.     }
  621.   else
  622.     {
  623.       low1 = D_HIGH_MAPLINE (last_diff, FILEC, FILE1, lowc);
  624.       high1 = D_HIGH_MAPLINE (last_diff, FILEC, FILE1, highc);
  625.     }
  626.  
  627.   /*
  628.    * Note that in the following, we use file 1 relative to the diff,
  629.    * and file 2 relative to the corresponding lines struct.
  630.    */
  631.   if (using[1])
  632.     {
  633.       low2 = D_LOW_MAPLINE (using[1], FILE0, FILE1, lowc);
  634.       high2 = D_HIGH_MAPLINE (last_using[1], FILE0, FILE1, highc); 
  635.     }
  636.   else
  637.     {
  638.       low2 = D_HIGH_MAPLINE (last_diff, FILEC, FILE2, lowc);
  639.       high2 = D_HIGH_MAPLINE (last_diff, FILEC, FILE2, highc);
  640.     }
  641.  
  642.   /* Create a block with the appropriate sizes */
  643.   result = create_diff3_block (lowc, highc, low1, high1, low2, high2);
  644.  
  645. #ifndef    DIRECT_DIFF
  646.   /* Copy over all of the information for File 0.  Return with a zero
  647.      if any of the compares failed. */
  648.   for (ptr = using[0]; ptr; ptr = D_NEXT (ptr))
  649.     {
  650.       LONG result_offset = D_LOWLINE (ptr, FILE0) - lowc;
  651.       LONG copy_size
  652.     = D_HIGHLINE (ptr, FILE0) - D_LOWLINE (ptr, FILE0) + 1;
  653.       
  654.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE0),
  655.                 D_LENARRAY (ptr, FILE0),
  656.                 D_LINEARRAY (result, FILEC) + result_offset,
  657.                 D_LENARRAY (result, FILEC) + result_offset,
  658.                 copy_size))
  659.     return 0;
  660.     }
  661.  
  662.   for (ptr = using[1]; ptr; ptr = D_NEXT (ptr))
  663.     {
  664.       LONG result_offset = D_LOWLINE (ptr, FILEC) - lowc;
  665.       LONG copy_size
  666.     = D_HIGHLINE (ptr, FILEC) - D_LOWLINE (ptr, FILEC) + 1;
  667.       
  668.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE0),
  669.                 D_LENARRAY (ptr, FILE0),
  670.                 D_LINEARRAY (result, FILEC) + result_offset,
  671.                 D_LENARRAY (result, FILEC) + result_offset,
  672.                 copy_size))
  673.     return 0;
  674.     }
  675.  
  676.   /* Copy stuff for file 1.  First deal with anything that might be
  677.      before the first diff. */
  678.  
  679.   for (i = 0;
  680.        i + low1 < (using[0] ? D_LOWLINE (using[0], FILE1) : high1 + 1);
  681.        i++)
  682.     {
  683.       D_RELNUM (result, FILE1, i) = D_RELNUM (result, FILEC, i);
  684.       D_RELLEN (result, FILE1, i) = D_RELLEN (result, FILEC, i);
  685.     }
  686.   
  687.   for (ptr = using[0]; ptr; ptr = D_NEXT (ptr))
  688.     {
  689.       LONG result_offset = D_LOWLINE (ptr, FILE1) - low1;
  690.       LONG copy_size
  691.     = D_HIGHLINE (ptr, FILE1) - D_LOWLINE (ptr, FILE1) + 1;
  692.  
  693.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE1),
  694.                 D_LENARRAY (ptr, FILE1),
  695.                 D_LINEARRAY (result, FILE1) + result_offset,
  696.                 D_LENARRAY (result, FILE1) + result_offset,
  697.                 copy_size))
  698.     return 0;
  699.  
  700.       /* Catch the lines between here and the next diff */
  701.       current0line = D_HIGHLINE (ptr, FILE0) + 1 - lowc;
  702.       for (i = D_HIGHLINE (ptr, FILE1) + 1 - low1;
  703.        i < (D_NEXT (ptr) ?
  704.         D_LOWLINE (D_NEXT (ptr), FILE1) :
  705.         high1 + 1) - low1;
  706.        i++)
  707.     {
  708.       D_RELNUM (result, FILE1, i)
  709.         = D_RELNUM (result, FILEC, current0line);
  710.       D_RELLEN (result, FILE1, i)
  711.         = D_RELLEN (result, FILEC, current0line++);
  712.     }
  713.     }
  714.  
  715.   /* Copy stuff for file 2.  First deal with anything that might be
  716.      before the first diff. */
  717.  
  718.   for (i = 0;
  719.        i + low2 < (using[1] ? D_LOWLINE (using[1], FILE1) : high2 + 1);
  720.        i++)
  721.     {
  722.       D_RELNUM (result, FILE2, i) = D_RELNUM (result, FILEC, i);
  723.       D_RELLEN (result, FILE2, i) = D_RELLEN (result, FILEC, i);
  724.     }
  725.   
  726.   for (ptr = using[1]; ptr; ptr = D_NEXT (ptr))
  727.     {
  728.       LONG result_offset = D_LOWLINE (ptr, FILE1) - low2;
  729.       LONG copy_size
  730.     = D_HIGHLINE (ptr, FILE1) - D_LOWLINE (ptr, FILE1) + 1;
  731.  
  732.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE1),
  733.                 D_LENARRAY (ptr, FILE1),
  734.                 D_LINEARRAY (result, FILE2) + result_offset,
  735.                 D_LENARRAY (result, FILE2) + result_offset,
  736.                 copy_size))
  737.     return 0;
  738.  
  739.       /* Catch the lines between here and the next diff */
  740.       current0line = D_HIGHLINE (ptr, FILE0) + 1 - lowc;
  741.       for (i = D_HIGHLINE (ptr, FILE1) + 1 - low2;
  742.        i < (D_NEXT (ptr) ?
  743.         D_LOWLINE (D_NEXT (ptr), FILE1) :
  744.         high2 + 1) - low2;
  745.        i++)
  746.     {
  747.       D_RELNUM (result, FILE2, i)
  748.         = D_RELNUM (result, FILEC, current0line);
  749.       D_RELLEN (result, FILE2, i)
  750.         = D_RELLEN (result, FILEC, current0line++);
  751.     }
  752.     }
  753. #endif    DIRECT_DIFF
  754.  
  755.   /* Set correspond */
  756.   if (!using[0])
  757.     D3_TYPE (result) = DIFF_3RD;
  758.   else if (!using[1])
  759.     D3_TYPE (result) = DIFF_2ND;
  760.   else
  761.     {
  762.         LONG nl1
  763.     = D_HIGHLINE (result, FILE1) - D_LOWLINE (result, FILE1) + 1;
  764.         LONG nl2
  765.     = D_HIGHLINE (result, FILE2) - D_LOWLINE (result, FILE2) + 1;
  766.  
  767. #ifdef    DIRECT_DIFF
  768.         D3_TYPE (result) = DIFF_1ST;
  769.         if ( nl1 != nl2 )
  770.             D3_TYPE (result) = DIFF_ALL;
  771.         else
  772.         {
  773.             if ( ! compare_line_list (diff3_file_data[FILE1].linbuf + D_LOWLINE (result, FILE1),
  774.                 diff3_file_data[FILE2].linbuf + D_LOWLINE (result, FILE2), nl1 ) )
  775.                     D3_TYPE (result) = DIFF_ALL;
  776.         }
  777. #else    DIRECT_DIFF
  778.       if (nl1 != nl2
  779.       || !compare_line_list (D_LINEARRAY (result, FILE1),
  780.                  D_LENARRAY (result, FILE1),
  781.                  D_LINEARRAY (result, FILE2),
  782.                  D_LENARRAY (result, FILE2),
  783.                  nl1))
  784.     D3_TYPE (result) = DIFF_ALL;
  785.       else
  786.     D3_TYPE (result) = DIFF_1ST;
  787. #endif    DIRECT_DIFF
  788.     }
  789.   
  790.   return result;
  791. }
  792.  
  793. #ifndef    DIRECT_DIFF
  794. /*
  795.  * This routine copies pointers from a list of strings to a different list
  796.  * of strings.  If a spot in the second list is already filled, it
  797.  * makes sure that it is filled with the same string; if not it
  798.  * returns 0, the copy incomplete.
  799.  * Upon successful completion of the copy, it returns 1.
  800.  */
  801. int
  802. copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum)
  803.      char *fromptrs[], *toptrs[];
  804.      LONG *fromlengths, *tolengths;
  805.      LONG copynum;
  806. {
  807.   register char
  808.     **f = fromptrs,
  809.     **t = toptrs;
  810.   register LONG
  811.     *fl = fromlengths,
  812.     *tl = tolengths;
  813.   
  814.   while (copynum--)
  815.     {
  816.       if (*t)
  817.     { if (*fl != *tl || bcmp (*f, *t, *fl)) return 0; }
  818.       else
  819.     { *t = *f ; *tl = *fl; }
  820.  
  821.       t++; f++; tl++; fl++;
  822.     }
  823.   return 1;
  824. }
  825. #endif    DIRECT_DIFF
  826.  
  827. /*
  828.  * Create a diff3_block, with ranges as specified in the arguments.
  829.  * Allocate the arrays for the various pointers (and zero them) based
  830.  * on the arguments passed.  Return the block as a result.
  831.  */
  832. struct diff3_block *
  833. create_diff3_block (low0, high0, low1, high1, low2, high2)
  834.     register LONG low0, high0, low1, high1, low2, high2;
  835. {
  836.   struct diff3_block *result = ALLOCATE (1, struct diff3_block);
  837.     LONG numlines;
  838.  
  839.   D3_TYPE (result) = ERROR;
  840.   D_NEXT (result) = 0;
  841.  
  842.   /* Assign ranges */
  843.   D_LOWLINE (result, FILE0) = low0;
  844.   D_HIGHLINE (result, FILE0) = high0;
  845.   D_LOWLINE (result, FILE1) = low1;
  846.   D_HIGHLINE (result, FILE1) = high1;
  847.   D_LOWLINE (result, FILE2) = low2;
  848.   D_HIGHLINE (result, FILE2) = high2;
  849.  
  850. #ifndef    DIRECT_DIFF
  851.   /* Allocate and zero space */
  852.   numlines = D_NUMLINES (result, FILE0);
  853.   if (numlines)
  854.     {
  855.       D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *);
  856.       D_LENARRAY (result, FILE0) = ALLOCATE (numlines, LONG);
  857.       bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *)));
  858.       bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (LONG)));
  859.     }
  860.   else
  861.     {
  862.       D_LINEARRAY (result, FILE0) = (char **) 0;
  863.       D_LENARRAY (result, FILE0) = (LONG *) 0;
  864.     }
  865.  
  866.   numlines = D_NUMLINES (result, FILE1);
  867.   if (numlines)
  868.     {
  869.       D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *);
  870.       D_LENARRAY (result, FILE1) = ALLOCATE (numlines, LONG);
  871.       bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *)));
  872.       bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (LONG)));
  873.     }
  874.   else
  875.     {
  876.       D_LINEARRAY (result, FILE1) = (char **) 0;
  877.       D_LENARRAY (result, FILE1) = (LONG *) 0;
  878.     }
  879.  
  880.   numlines = D_NUMLINES (result, FILE2);
  881.   if (numlines)
  882.     {
  883.       D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *);
  884.       D_LENARRAY (result, FILE2) = ALLOCATE (numlines, LONG);
  885.       bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *)));
  886.       bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (LONG)));
  887.     }
  888.   else
  889.     {
  890.       D_LINEARRAY (result, FILE2) = (char **) 0;
  891.       D_LENARRAY (result, FILE2) = (LONG *) 0;
  892.     }
  893. #endif    DIRECT_DIFF
  894.  
  895.   /* Return */
  896.   return result;
  897. }
  898.  
  899. #ifndef    DIRECT_DIFF
  900. /*
  901.  * Compare two lists of lines of text.
  902.  * Return 1 if they are equivalent, 0 if not.
  903.  */
  904. int
  905. compare_line_list (list1, lengths1, list2, lengths2, nl)
  906.      char *list1[], *list2[];
  907.      LONG *lengths1, *lengths2;
  908.      LONG nl;
  909. {
  910.   char
  911.     **l1 = list1,
  912.     **l2 = list2;
  913.   LONG
  914.     *lgths1 = lengths1,
  915.     *lgths2 = lengths2;
  916.   
  917.   while (nl--)
  918.     if (!*l1 || !*l2 || *lgths1 != *lgths2++
  919.     || bcmp (*l1++, *l2++, *lgths1++))
  920.       return 0;
  921.   return 1;
  922. }
  923. #else    DIRECT_DIFF
  924.  
  925. /*
  926.  * Compare two lists of lines of text.
  927.  * Return 1 if they are equivelent, 0 if not.
  928.  */
  929. static    int
  930. compare_line_list (list1, list2, nl)
  931.     struct line_def list1[], list2[];
  932.     LONG nl;
  933. {
  934.     struct line_def *l1 = list1, *l2 = list2;
  935.     
  936.     while (nl--)
  937.     {
  938.         /* if (!l1->text || !l2->text || l1->length != l2->length
  939.             || bcmp (l1->text, l2->text, l1->length))
  940.                 return 0; */
  941.         /* The following lines (in place of above) will use the various "ignore" flags in the comparison! */
  942.         /* Note that they are not set when the diff3 algorithm is called from "main".  This is only for
  943.            a future extension */
  944.         if ( ! l1->text || ! l2->text || line_cmp(l1, l2) )
  945.             return 0;
  946.         l1++;
  947.         l2++;
  948.     }
  949.     return 1;
  950. }
  951. #endif    DIRECT_DIFF
  952.  
  953. #ifndef    DIRECT_DIFF
  954. /* 
  955.  * Routines to input and parse two way diffs.
  956.  */
  957.  
  958. extern char **environ;
  959.  
  960. #define    DIFF_CHUNK_SIZE    10000
  961.  
  962. struct diff_block *
  963. process_diff (filea, fileb)
  964.      char *filea, *fileb;
  965. {
  966.   char *diff_contents;
  967.   char *diff_limit;
  968.   char *scan_diff;
  969.   enum diff_type dt;
  970.   LONG i;
  971.   struct diff_block *block_list, *block_list_end, *bptr;
  972.  
  973.   diff_limit = read_diff (filea, fileb, &diff_contents);
  974.   scan_diff = diff_contents;
  975.   bptr = block_list_end = block_list = (struct diff_block *) 0;
  976.  
  977.   while (scan_diff < diff_limit)
  978.     {
  979.       bptr = ALLOCATE (1, struct diff_block);
  980.       bptr->next = 0;
  981.       bptr->lines[0] = bptr->lines[1] = (char **) 0;
  982.       bptr->lengths[0] = bptr->lengths[1] = (LONG *) 0;
  983.       
  984.       dt = process_diff_control (&scan_diff, bptr);
  985.       if (dt == ERROR || *scan_diff != '\n')
  986.     {
  987.       fpout (stderr, "%s: diff error: ", argv0);
  988.       do
  989.         {
  990.           petec (*scan_diff, stderr);
  991.         }
  992.       while (*scan_diff++ != '\n');
  993.       exit (2);
  994.     }
  995.       scan_diff++;
  996.       
  997.       /* Force appropriate ranges to be null, if necessary */
  998.       switch (dt)
  999.     {
  1000.     case ADD:
  1001.       bptr->ranges[0][0]++;
  1002.       break;
  1003.     case DELETE:
  1004.       bptr->ranges[1][0]++;
  1005.       break;
  1006.     case CHANGE:
  1007.       break;
  1008.     default:
  1009.       fatal ("internal: Bad diff type in process_diff");
  1010.       break;
  1011.     }
  1012.       
  1013.       /* Allocate space for the pointers for the lines from filea, and
  1014.      parcel them out among these pointers */
  1015.       if (dt != ADD)
  1016.     {
  1017.       bptr->lines[0] = ALLOCATE ((bptr->ranges[0][END]
  1018.                       - bptr->ranges[0][START] + 1),
  1019.                      char *);
  1020.       bptr->lengths[0] = ALLOCATE ((bptr->ranges[0][END]
  1021.                     - bptr->ranges[0][START] + 1),
  1022.                        LONG);
  1023.       for (i = 0; i <= (bptr->ranges[0][END]
  1024.                 - bptr->ranges[0][START]); i++)
  1025.         scan_diff = scan_diff_line (scan_diff,
  1026.                     &(bptr->lines[0][i]),
  1027.                     &(bptr->lengths[0][i]),
  1028.                     diff_limit,
  1029.                     '<');
  1030.     }
  1031.       
  1032.       /* Get past the separator for changes */
  1033.       if (dt == CHANGE)
  1034.     {
  1035.       if (strncmp (scan_diff, "---\n", 4))
  1036.         fatal ("Bad diff format: bad change separator");
  1037.       scan_diff += 4;
  1038.     }
  1039.       
  1040.       /* Allocate space for the pointers for the lines from fileb, and
  1041.      parcel them out among these pointers */
  1042.       if (dt != DELETE)
  1043.     {
  1044.       bptr->lines[1] = ALLOCATE ((bptr->ranges[1][END]
  1045.                       - bptr->ranges[1][START] + 1),
  1046.                      char *);
  1047.       bptr->lengths[1] = ALLOCATE ((bptr->ranges[1][END]
  1048.                     - bptr->ranges[1][START] + 1),
  1049.                        LONG);
  1050.       for (i = 0; i <= (bptr->ranges[1][END]
  1051.                 - bptr->ranges[1][START]); i++)
  1052.         scan_diff = scan_diff_line (scan_diff,
  1053.                     &(bptr->lines[1][i]),
  1054.                     &(bptr->lengths[1][i]),
  1055.                     diff_limit,
  1056.                     '>');
  1057.     }
  1058.       
  1059.       /* Place this block on the blocklist */
  1060.       if (block_list_end)
  1061.     block_list_end->next = bptr;
  1062.       else
  1063.     block_list = bptr;
  1064.       
  1065.       block_list_end = bptr;
  1066.       
  1067.     }
  1068.  
  1069.   return block_list;
  1070. }
  1071.  
  1072. /*
  1073.  * This routine will parse a normal format diff control string.  It
  1074.  * returns the type of the diff (ERROR if the format is bad).  All of
  1075.  * the other important information is filled into to the structure
  1076.  * pointed to by db, and the string pointer (whose location is passed
  1077.  * to this routine) is updated to point beyond the end of the string
  1078.  * parsed.  Note that only the ranges in the diff_block will be set by
  1079.  * this routine.
  1080.  *
  1081.  * If some specific pair of numbers has been reduced to a single
  1082.  * number, then both corresponding numbers in the diff block are set
  1083.  * to that number.  In general these numbers are interpetted as ranges
  1084.  * inclusive, unless being used by the ADD or DELETE commands.  It is
  1085.  * assumed that these will be special cased in a superior routine.  
  1086.  */
  1087.  
  1088. enum diff_type
  1089. process_diff_control (string, db)
  1090.      char **string;
  1091.      struct diff_block *db;
  1092. {
  1093.   char *s = *string;
  1094.   LONG holdnum;
  1095.   enum diff_type type;
  1096.  
  1097. /* These macros are defined here because they can use variables
  1098.    defined in this function.  Don't try this at home kids, we're
  1099.    trained professionals!
  1100.  
  1101.    Also note that SKIPWHITE only recognizes tabs and spaces, and
  1102.    that READNUM can only read positive, integral numbers */
  1103.  
  1104. #define    SKIPWHITE(s)    { while (*s == ' ' || *s == '\t') s++; }
  1105. #define    READNUM(s, num)    \
  1106.     { if (!isdigit (*s)) return ERROR; holdnum = 0;    \
  1107.       do { holdnum = (*s++ - '0' + holdnum * 10); }    \
  1108.       while (isdigit (*s)); (num) = holdnum; }
  1109.  
  1110.   /* Read first set of digits */
  1111.   SKIPWHITE (s);
  1112.   READNUM (s, db->ranges[0][START]);
  1113.  
  1114.   /* Was that the only digit? */
  1115.   SKIPWHITE(s);
  1116.   if (*s == ',')
  1117.     {
  1118.       /* Get the next digit */
  1119.       s++;
  1120.       READNUM (s, db->ranges[0][END]);
  1121.     }
  1122.   else
  1123.     db->ranges[0][END] = db->ranges[0][START];
  1124.  
  1125.   /* Get the letter */
  1126.   SKIPWHITE (s);
  1127.   switch (*s)
  1128.     {
  1129.     case 'a':
  1130.       type = ADD;
  1131.       break;
  1132.     case 'c':
  1133.       type = CHANGE;
  1134.       break;
  1135.     case 'd':
  1136.       type = DELETE;
  1137.       break;
  1138.     default:
  1139.       return ERROR;            /* Bad format */
  1140.     }
  1141.   s++;                /* Past letter */
  1142.   
  1143.   /* Read second set of digits */
  1144.   SKIPWHITE (s);
  1145.   READNUM (s, db->ranges[1][START]);
  1146.  
  1147.   /* Was that the only digit? */
  1148.   SKIPWHITE(s);
  1149.   if (*s == ',')
  1150.     {
  1151.       /* Get the next digit */
  1152.       s++;
  1153.       READNUM (s, db->ranges[1][END]);
  1154.       SKIPWHITE (s);        /* To move to end */
  1155.     }
  1156.   else
  1157.     db->ranges[1][END] = db->ranges[1][START];
  1158.  
  1159.   *string = s;
  1160.   return type;
  1161. }
  1162.  
  1163. char *
  1164. read_diff (filea, fileb, output_placement)
  1165.      char *filea, *fileb;
  1166.      char **output_placement;
  1167. {
  1168.   char *argv[6];
  1169.   char **ap;
  1170.   int fds[2];
  1171.   char *diff_result;
  1172.   LONG current_chunk_size;
  1173.   LONG bytes;
  1174.   LONG total;
  1175.   int pid, w;
  1176.   int wstatus;
  1177.  
  1178.   ap = argv;
  1179.   *ap++ = diff_program;
  1180.   if (always_text)
  1181.     *ap++ = "-a";
  1182.   *ap++ = "--";
  1183.   *ap++ = filea;
  1184.   *ap++ = fileb;
  1185.   *ap = (char *) 0;
  1186.  
  1187.   if (pipe (fds) < 0)
  1188.     perror_with_exit ("Pipe failed");
  1189.  
  1190.   pid = vfork ();
  1191.   if (pid == 0)
  1192.     {
  1193.       /* Child */
  1194.       close (fds[0]);
  1195.       if (fds[1] != fileno (stdout))
  1196.     {
  1197.       dup2 (fds[1], fileno (stdout));
  1198.       close (fds[1]);
  1199.     }
  1200.       execve (diff_program, argv, environ);
  1201.       /* Avoid stdio, because the parent process's buffers are inherited. */
  1202.       write (fileno (stderr), diff_program, strlen (diff_program));
  1203.       write (fileno (stderr), ": not found\n", 12);
  1204.       _exit (2);
  1205.     }
  1206.  
  1207.   if (pid == -1)
  1208.     perror_with_exit ("Fork failed");
  1209.  
  1210.   close (fds[1]);        /* Prevent erroneous lack of EOF */
  1211.   current_chunk_size = DIFF_CHUNK_SIZE;
  1212.   diff_result = (char *) xmalloc (current_chunk_size);
  1213.   total = 0;
  1214.   do {
  1215.     bytes = myread (fds[0],
  1216.             diff_result + total,
  1217.             current_chunk_size - total);
  1218.     total += bytes;
  1219.     if (total == current_chunk_size)
  1220.       diff_result = (char *) xrealloc (diff_result, (current_chunk_size *= 2));
  1221.   } while (bytes);
  1222.  
  1223.   if (total != 0 && diff_result[total-1] != '\n')
  1224.     fatal ("bad diff format; incomplete last line");
  1225.  
  1226.   *output_placement = diff_result;
  1227.  
  1228.   do
  1229.     if ((w = wait (&wstatus)) == -1)
  1230.       perror_with_exit ("Wait failed");
  1231.   while (w != pid);
  1232.  
  1233.   if (! (WIFEXITED (wstatus) && WEXITSTATUS (wstatus) < 2))
  1234.     fatal ("Subsidiary diff failed");
  1235.  
  1236.   return diff_result + total;
  1237. }
  1238.  
  1239.  
  1240. /*
  1241.  * Scan a regular diff line (consisting of > or <, followed by a
  1242.  * space, followed by text (including nulls) up to a newline.
  1243.  *
  1244.  * This next routine began life as a macro and many parameters in it
  1245.  * are used as call-by-reference values.
  1246.  */
  1247. char *
  1248. scan_diff_line (scan_ptr, set_start, set_length, limit, firstchar)
  1249.      char *scan_ptr, **set_start;
  1250.      LONG *set_length;
  1251.      char *limit;
  1252.      char firstchar;
  1253. {
  1254.   char *line_ptr;
  1255.  
  1256.   if (!(scan_ptr[0] == (firstchar)
  1257.     && scan_ptr[1] == ' '))
  1258.     fatal ("Bad diff format; incorrect leading line chars");
  1259.  
  1260.   *set_start = line_ptr = scan_ptr + 2;
  1261.   while (*line_ptr++ != '\n')
  1262.     ;
  1263.  
  1264.   /* Include newline if the original line ended in a newline,
  1265.      or if an edit script is being generated.
  1266.      Copy any missing newline message to stderr if an edit script is being
  1267.      generated, because edit scripts cannot handle missing newlines.
  1268.      Return the beginning of the next line.  */
  1269.   *set_length = line_ptr - *set_start;
  1270.   if (line_ptr < limit && *line_ptr == '\\')
  1271.     {
  1272.       if (edscript)
  1273.     fpout (stderr, "%s:", argv0);
  1274.       else
  1275.     --*set_length;
  1276.       line_ptr++;
  1277.       do
  1278.     {
  1279.       if (edscript)
  1280.         petec (*line_ptr, stderr);
  1281.     }
  1282.       while (*line_ptr++ != '\n');
  1283.     }
  1284.  
  1285.   return line_ptr;
  1286. }
  1287. #endif    DIRECT_DIFF
  1288.  
  1289. /*
  1290.  * This routine outputs a three way diff passed as a list of
  1291.  * diff3_block's.
  1292.  * The argument MAPPING is indexed by external file number (in the
  1293.  * argument list) and contains the internal file number (from the
  1294.  * diff passed).  This is important because the user expects his
  1295.  * outputs in terms of the argument list number, and the diff passed
  1296.  * may have been done slightly differently (if the first argument in
  1297.  * the argument list was the standard input, for example).
  1298.  * REV_MAPPING is the inverse of MAPPING.
  1299.  */
  1300. void
  1301. output_diff3 (outputfile, diff, mapping, rev_mapping)
  1302.     FILE *outputfile;
  1303.      struct diff3_block *diff;
  1304.     int mapping[3], rev_mapping[3];
  1305. {
  1306.     int i;
  1307.   int oddoneout;
  1308.   char *cp;
  1309.   struct diff3_block *ptr;
  1310.     LONG line;
  1311.     LONG length;
  1312.   int dontprint;
  1313.   static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
  1314.  
  1315.   for (ptr = diff; ptr; ptr = D_NEXT (ptr))
  1316.     {
  1317.       char x[2];
  1318.  
  1319.       switch (ptr->correspond)
  1320.     {
  1321.     case DIFF_ALL:
  1322.       x[0] = '\0';
  1323.       dontprint = 3;    /* Print them all */
  1324.       oddoneout = 3;    /* Nobody's odder than anyone else */
  1325.       break;
  1326.     case DIFF_1ST:
  1327.     case DIFF_2ND:
  1328.     case DIFF_3RD:
  1329.       oddoneout = rev_mapping [(int) ptr->correspond - (int) DIFF_1ST];
  1330.         
  1331.       x[0] = oddoneout + '1';
  1332.       x[1] = '\0';
  1333.       dontprint = oddoneout==0;
  1334.       break;
  1335.     default:
  1336.       fatal ("internal: Bad diff type passed to output");
  1337.             return;    /* Not much we can do but exit.  Luckily, the diff stuff is already finished. */
  1338.     }
  1339.         fpout (outputfile, "====%s\n", x);
  1340.  
  1341.       /* Go 0, 2, 1 if the first and third outputs are equivalent. */
  1342.       for (i = 0; i < 3;
  1343.        i = (oddoneout == 1 ? skew_increment[i] : i + 1))
  1344.     {
  1345.             int realfile = mapping[i];
  1346.             LONG
  1347.         lowt = D_LOWLINE (ptr, realfile),
  1348.         hight = D_HIGHLINE (ptr, realfile);
  1349.       
  1350.             fpout (outputfile, "%d:", i + 1);
  1351.       switch (lowt - hight)
  1352.         {
  1353.         case 1:
  1354.                 fpout (outputfile, "%lda\n", (long)lowt - 1);
  1355.           break;
  1356.         case 0:
  1357.                 fpout (outputfile, "%ldc\n", (long)lowt);
  1358.           break;
  1359.         default:
  1360.                 fpout (outputfile, "%ld,%ldc\n", (long)lowt, (long)hight);
  1361.           break;
  1362.         }
  1363.  
  1364.       if (i == dontprint) continue;
  1365.  
  1366.       for (line = 0; line < hight - lowt + 1; line++)
  1367.         {
  1368.           fpout (outputfile, "  ");
  1369.           cp = D_RELNUM (ptr, realfile, line);
  1370.           length = D_RELLEN (ptr, realfile, line);
  1371.           pwrite (cp, sizeof (char), length, outputfile);
  1372.         }
  1373.       if (line != 0 && cp[length - 1] != NEWLINE)
  1374.         fpout (outputfile, "\n\\ No newline at end of file\n");
  1375.     }
  1376.     }
  1377. }
  1378.  
  1379. /*
  1380.  * This routine outputs a diff3 set of blocks as an ed script.  This
  1381.  * script applies the changes between file's 2 & 3 to file 1.  It
  1382.  * takes the precise format of the ed script to be output from global
  1383.  * variables set during options processing.  Note that it does
  1384.  * destructive things to the set of diff3 blocks it is passed; it
  1385.  * reverses their order (this gets around the problems involved with
  1386.  * changing line numbers in an ed script).
  1387.  *
  1388.  * Note that this routine has the same problem of mapping as the last
  1389.  * one did; the variable MAPPING maps from file number according to
  1390.  * the argument list to file number according to the diff passed.  All
  1391.  * files listed below are in terms of the argument list.
  1392.  * REV_MAPPING is the inverse of MAPPING.
  1393.  *
  1394.  * The arguments FILE0, FILE1 and FILE2 are the strings to print
  1395.  * as the names of the three files.  These may be the actual names,
  1396.  * or may be the arguments specified with -L.
  1397.  *
  1398.  * Returns 1 if overlaps were found.
  1399.  */
  1400.  
  1401. int
  1402. output_diff3_edscript (outputfile, diff,  mapping, rev_mapping,
  1403.                 file0, file1, file2)
  1404.      FILE *outputfile;
  1405.      struct diff3_block *diff;
  1406.     int mapping[3], rev_mapping[3];
  1407.      char *file0, *file1, *file2;
  1408. {
  1409.     LONG i;
  1410.   int leading_dot;
  1411.   int overlaps_found = 0;
  1412.   struct diff3_block *newblock, *thisblock;
  1413.  
  1414.   leading_dot = 0;
  1415.  
  1416.   newblock = reverse_diff3_blocklist (diff);
  1417.  
  1418.     for (thisblock = newblock; thisblock; thisblock = thisblock->next)
  1419.     {
  1420.       /* Must do mapping correctly.  */
  1421.       enum diff_type type
  1422.     = ((thisblock->correspond == DIFF_ALL) ?
  1423.        DIFF_ALL :
  1424.        ((enum diff_type)
  1425.         (((int) DIFF_1ST)
  1426.          + rev_mapping [(int) thisblock->correspond - (int) DIFF_1ST] )));
  1427.  
  1428.       /* If we aren't supposed to do this output block, skip it */
  1429.       if (type == DIFF_2ND || type == DIFF_1ST
  1430.       || (type == DIFF_3RD && dont_write_simple)
  1431.       || (type == DIFF_ALL && dont_write_overlap))
  1432.     continue;
  1433.  
  1434.       if (flagging && type == DIFF_ALL)
  1435.     /* Do special flagging */
  1436.     {
  1437.  
  1438.       /* Put in lines from FILE2 with bracket */
  1439.             fpout (outputfile, "%lda\n",
  1440.                 (long)D_HIGHLINE (thisblock, mapping[FILE0]));
  1441.             fpout (outputfile, "=======\n");
  1442.       for (i = 0;
  1443.                 i < D_NUMLINES (thisblock, mapping [FILE2]);
  1444.            i++)
  1445.         {
  1446.                 if (D_RELNUM (thisblock, mapping [FILE2], i)[0] == '.')
  1447.         { leading_dot = 1; fpout(outputfile, "."); }
  1448.           pwrite (D_RELNUM (thisblock, mapping[FILE2], i), sizeof (char),
  1449.               D_RELLEN (thisblock, mapping[FILE2], i), outputfile);
  1450.         }
  1451.             fpout (outputfile, ">>>>>>> %s\n.\n", file2);
  1452.       overlaps_found = 1;
  1453.  
  1454.       /* Add in code to take care of leading dots, if necessary. */
  1455.       if (leading_dot)
  1456.         {
  1457.                 fpout (outputfile, "%ld,%lds/^\\.\\./\\./\n",
  1458.                     (long)D_HIGHLINE (thisblock, mapping [FILE0]) + 1,
  1459.                     (long)(D_HIGHLINE (thisblock, mapping [FILE0])
  1460.                         + D_NUMLINES (thisblock, mapping [FILE2])));
  1461.           leading_dot = 0;
  1462.         }
  1463.  
  1464.       /* Put in code to do initial bracket of lines from FILE0  */
  1465.             fpout (outputfile, "%lda\n<<<<<<< %s\n.\n",
  1466.                 (long)D_LOWLINE (thisblock, mapping [FILE0]) - 1,
  1467.            file0);
  1468.     }
  1469.         else if (D_NUMLINES (thisblock, mapping [FILE2]) == 0)
  1470.     /* Write out a delete */
  1471.     {
  1472.             if (D_NUMLINES (thisblock, mapping [FILE0]) == 1)
  1473.                 fpout (outputfile, "%ldd\n",
  1474.                     (long)D_LOWLINE (thisblock, mapping [FILE0]));
  1475.       else
  1476.                 fpout (outputfile, "%ld,%ldd\n",
  1477.                     (long)D_LOWLINE (thisblock, mapping [FILE0]),
  1478.                     (long)D_HIGHLINE (thisblock, mapping [FILE0]));
  1479.     }
  1480.       else
  1481.     /* Write out an add or change */
  1482.     {
  1483.             switch (D_NUMLINES (thisblock, mapping [FILE0]))
  1484.         {
  1485.         case 0:
  1486.                 fpout (outputfile, "%lda\n",
  1487.                     (long)D_HIGHLINE (thisblock, mapping [FILE0]));
  1488.           break;
  1489.         case 1:
  1490.                 fpout (outputfile, "%ldc\n",
  1491.                     (long)D_HIGHLINE (thisblock, mapping [FILE0]));
  1492.           break;
  1493.         default:
  1494.                 fpout (outputfile, "%ld,%ldc\n",
  1495.                     (long)D_LOWLINE (thisblock, mapping [FILE0]),
  1496.                     (long)D_HIGHLINE (thisblock, mapping [FILE0]));
  1497.           break;
  1498.         }
  1499.       for (i = 0;
  1500.                 i < D_NUMLINES (thisblock, mapping [FILE2]);
  1501.            i++)
  1502.         {
  1503.           if (D_RELNUM (thisblock, mapping[FILE2], i)[0] == '.')
  1504.         { leading_dot = 1; fpout (outputfile, "."); }
  1505.           pwrite (D_RELNUM (thisblock, mapping[FILE2], i), sizeof (char),
  1506.               D_RELLEN (thisblock, mapping[FILE2], i), outputfile);
  1507.         }
  1508.             fpout (outputfile, ".\n");
  1509.       
  1510.       /* Add in code to take care of leading dots, if necessary. */
  1511.       if (leading_dot)
  1512.         {
  1513.                 fpout (outputfile, "%ld,%lds/^\\.\\./\\./\n",
  1514.                     (long)D_HIGHLINE (thisblock, mapping [FILE0]) + 1,
  1515.                     (long)(D_HIGHLINE (thisblock, mapping [FILE0])
  1516.                         + D_NUMLINES (thisblock, mapping [FILE2])));
  1517.           leading_dot = 0;
  1518.         }
  1519.     }
  1520.     }
  1521.     if (finalwrite) fpout (outputfile, "w\nq\n");
  1522.   return overlaps_found;
  1523. }
  1524.  
  1525. #ifndef    EXCLUDE_MAIN
  1526.  
  1527. /*
  1528.  * Read from COMMONFILE and output to OUTPUTFILE a set of diff3_ blocks DIFF
  1529.  * as a merged file.  This acts like 'ed file0 <[output_diff3_edscript]',
  1530.  * except that it works even for binary data or incomplete lines.
  1531.  *
  1532.  * As before, MAPPING maps from arg list file number to diff file number,
  1533.  * REV_MAPPING is its inverse,
  1534.  * and FILE0, FILE1, and FILE2 are the names of the files.
  1535.  *
  1536.  * Returns 1 if overlaps were found.
  1537.  */
  1538.  
  1539. int
  1540. output_diff3_merge (commonfile, outputfile, diff, mapping, rev_mapping,
  1541.             file0, file1, file2)
  1542.      FILE *commonfile, *outputfile;
  1543.      struct diff3_block *diff;
  1544.      int mapping[3], rev_mapping[3];
  1545.      char *file0, *file1, *file2;
  1546. {
  1547.   int c;
  1548.   LONG i;
  1549.   int overlaps_found = 0;
  1550.   struct diff3_block *b;
  1551.   LONG linesread = 0;
  1552.  
  1553.   for (b = diff; b; b = b->next)
  1554.     {
  1555.       /* Must do mapping correctly */
  1556.       enum diff_type type
  1557.     = ((b->correspond == DIFF_ALL) ?
  1558.        DIFF_ALL :
  1559.        ((enum diff_type)
  1560.         (((int) DIFF_1ST)
  1561.          + rev_mapping[(int) b->correspond - (int) DIFF_1ST])));
  1562.  
  1563.       /* If we aren't supposed to do this output block, skip it.  */
  1564.       if (type == DIFF_2ND || type == DIFF_1ST
  1565.       || (type == DIFF_3RD && dont_write_simple)
  1566.       || (type == DIFF_ALL && dont_write_overlap))
  1567.     continue;
  1568.  
  1569.       /* Copy I lines from common file.  */
  1570.       i = D_LOWLINE (b, FILE0) - linesread - 1;
  1571.       linesread += i;
  1572.       while (0 <= --i)
  1573.     {
  1574.       while ((c = getc(commonfile)) != '\n')
  1575.         {
  1576.           if (c == EOF)
  1577.         fatal ("input file shrank");
  1578.           petec (c, outputfile);
  1579.         }
  1580.       petec (c, outputfile);
  1581.     }
  1582.  
  1583.       if (flagging && type == DIFF_ALL)
  1584.     /* Do special flagging.  */
  1585.     {
  1586.       /* Put in lines from FILE0 with bracket.  */
  1587.       fpout (outputfile, "<<<<<<< %s\n", file0);
  1588.       for (i = 0;
  1589.            i < D_NUMLINES (b, mapping[FILE0]);
  1590.            i++)
  1591.         pwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
  1592.             D_RELLEN (b, mapping[FILE0], i), outputfile);
  1593.       fpout (outputfile, "=======\n");
  1594.       overlaps_found = 1;
  1595.     }
  1596.  
  1597.       /* Put in lines from FILE2.  */
  1598.       for (i = 0;
  1599.        i < D_NUMLINES (b, mapping[FILE2]);
  1600.        i++)
  1601.     pwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
  1602.         D_RELLEN (b, mapping[FILE2], i), outputfile);
  1603.  
  1604.       if (flagging && type == DIFF_ALL)
  1605.     fpout (outputfile, ">>>>>>> %s\n", file2);
  1606.  
  1607.       /* Skip I lines in common file.  */
  1608.       i = D_NUMLINES (b, FILE0);
  1609.       linesread += i;
  1610.       while (0 <= --i)
  1611.     while ((c = getc(commonfile)) != '\n')
  1612.       if (c == EOF)
  1613.         {
  1614.           if (i || b->next)
  1615.         fatal ("input file shrank");
  1616.           return overlaps_found;
  1617.         }
  1618.     }
  1619.   /* Copy rest of common file.  */
  1620.   while ((c = getc (commonfile)) != EOF)
  1621.     petec (c, outputfile);
  1622.   return overlaps_found;
  1623. }
  1624.  
  1625. #endif    EXCLUDE_MAIN
  1626.  
  1627. /*
  1628.  * Reverse the order of the list of diff3 blocks.
  1629.  */
  1630. struct diff3_block *
  1631. reverse_diff3_blocklist (diff)
  1632.      struct diff3_block *diff;
  1633. {
  1634.   register struct diff3_block *tmp, *next, *prev;
  1635.  
  1636.   for (tmp = diff, prev = (struct diff3_block *) 0;
  1637.        tmp; tmp = next)
  1638.     {
  1639.         next = tmp->next;
  1640.         tmp->next = prev;
  1641.       prev = tmp;
  1642.     }
  1643.   
  1644.   return prev;
  1645. }
  1646.  
  1647. #ifndef    EXCLUDE_MAIN
  1648. static    LONG
  1649. myread (fd, ptr, size)
  1650.     int fd;
  1651.     LONG size;
  1652.      char *ptr;
  1653. {
  1654.     LONG result;
  1655.     int    i;
  1656.  
  1657.     while ( size > 0 )
  1658.     {
  1659.         i = read (fd, ptr, size> 32000? 32000: size);
  1660.         if (i < 0)
  1661.     perror_with_exit ("Read failed");
  1662.         size -= i;
  1663.         ptr += i;
  1664.         result += i;
  1665.     }
  1666.   return result;
  1667. }
  1668.  
  1669. #ifndef    DIRECT_DIFF    /* UTIL.C has these functions */
  1670. VOID *
  1671. xmalloc (size)
  1672.     size_t size;
  1673. {
  1674.     VOID *result = (VOID *) malloc ((size_t)1, size ? size : 1);
  1675.   if (!result)
  1676.     fatal ("Malloc failed");
  1677.   return result;
  1678. }
  1679.  
  1680. VOID *
  1681. xrealloc (ptr, size)
  1682.     VOID *ptr;
  1683.     size_t size;
  1684. {
  1685.   VOID *result = (VOID *) realloc (ptr, size ? size : 1);
  1686.   if (!result)
  1687.     fatal ("Malloc failed");
  1688.   return result;
  1689. }
  1690. #endif    DIRECT_DIFF
  1691.  
  1692. static    void
  1693. fatal (string)
  1694.      char *string;
  1695. {
  1696.   fpout (stderr, "%s: %s\n", argv0, string);
  1697.   exit (2);
  1698. }
  1699.  
  1700. perror_with_exit (string)
  1701.      char *string;
  1702. {
  1703.   fpout (stderr, "%s", string);
  1704.   exit (2);
  1705. }
  1706. #endif    EXCLUDE_MAIN
  1707.  
  1708.